package g

/*
 * @lc app=leetcode.cn id=14 lang=golang
 *
 * [14] 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
*/

// @lc code=start
func longestCommonPrefix(strs []string) string {
	return longestCommonPrefixBinary(strs)
}

func longestCommonPrefixSplit(strs []string) string {
	if len(strs) == 0 {
		return ""
	}

	str := getMinSize(strs)
	for {
		var i int
		for i < len(strs) {
			if str != strs[i][0:len(str)] {
				str = str[0 : len(str)-1]
				break
			}
			i++
		}
		if i == len(strs) {
			break
		}
	}

	return str
}

func longestCommonPrefixBinary(strs []string) string {
	if len(strs) == 0 {
		return ""
	}

	length := len(getMinSize(strs))
	var end int
	for length > 0 {
		midLen := (length + 1) / 2
		str := strs[0][end : midLen+end]
		var i int
		for i < len(strs) {
			if str != strs[i][end:len(str)+end] {
				break
			}
			i++
		}
		if i == len(strs) {
			end += midLen
		}
		length /= 2
	}

	return strs[0][0:end]
}

func getMinSize(strs []string) string {
	str := strs[0]
	for i := 1; i < len(strs); i++ {
		if len(str) > len(strs[i]) {
			str = strs[i]
		}
	}
	return str
}

// @lc code=end
